package com.lijing.integerPartition;

/**
 * @Description TODO
 * @title: IntegerPartition01
 * @Author LiJing
 * @Date: 2021/4/67:00 下午
 * @Version 1.0
 */
public class IntegerPartition01 {
    public static void main(String[] args) {
        int n = 11;
        System.out.println(integerPartition(n));
        System.out.println(integerPartition2(n));
    }

    public static int integerPartition(int n){
        /*
         * @Date: 2021/4/6 7:05 下午
         * Step 1: 确定状态
         * maxProduct[i]表示i拆分为至少两个正整数后，正整数的最大乘积
         */
        int[] maxProduct = new int[n+1];
        /*
         * @Date: 2021/4/6 7:07 下午
         * Step 2: 状态转移方程,并初始化
         * f[i] = max(f[i],max(j*(i-j),j*f[i-j]))
         */
        maxProduct[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i-1; j++) {
                maxProduct[i] = Math.max(maxProduct[i],Math.max((i-j)*j, j*maxProduct[i-j]));
            }
        }
        return maxProduct[n];
    }

    /**
     *
     * @param n n
     * @return 返回最大乘积
     */
    public static int integerPartition2(int n){
        if (n == 2){
            return 1;
        }
        if (n == 3){
            return 2;
        }
        if (n == 4){
            return 4;
        }
        int result = 1;
        while (n > 4){
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
}
